#include <iostream>
#include <stack>

struct TreeNode
{
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;

    int val = 0;
};

// class Solution {
//     void preorder(TreeNode* root, std::vector<TreeNode*>& v)
//     {
//         if(root == nullptr)
//             return;

//         v.push_back(root);
//         preorder(root->left, v);
//         preorder(root->right, v);
//     }
// public:
//     void flatten(TreeNode* root) {
//         std::vector<TreeNode*> v;
//         //先序遍历存放在数组里
//         preorder(root, v);
//         v.push_back(nullptr);

//         for(int i = 0; i < v.size() - 1; i++)
//         {
//             v[i]->right = v[i + 1];
//             v[i]->left = nullptr;
//         }
//     }
// };

class Solution
{
public:
    void flatten(TreeNode* root) {
        if(root == nullptr)
            return;

        std::stack<TreeNode*> st;
        st.push(root);

        TreeNode* prev = nullptr;
        while(!st.empty())
        {
            TreeNode* cur = st.top();
            st.pop();

            if(prev != nullptr)
            {
                prev->right = cur;
                prev->left = nullptr;
            }

            //右面不为空
            if(cur->right != nullptr)
            {
                st.push(cur->right);
            }
            //左面不为空
            if(cur->left != nullptr)
            {
                st.push(cur->left);
            }
            prev = cur;
        }
    }

};